package datastructure;

class RMQ {
	int rmq[][], pow2[], a[];

	public void initRMQ(int[] array) {
		a = array;
		int n = a.length;
		int max = 1;
		while (max <= n)
			max *= 2;
		int k = (int) (Math.log10(n) / Math.log10(2)) + 1;
		rmq = new int[max][k];
		pow2 = new int[k];
		pow2[0] = 1;
		for (int i = 1; i < k; i++)
			pow2[i] = pow2[i - 1] * 2;
		for (int i = 0; i < n; i++)
			rmq[i][0] = i;
		for (int i = 1; i < k; i++) {
			int t = n - pow2[i];
			for (int j = 0; j <= t; j++) {
				rmq[j][i] = compare(rmq[j][i - 1], rmq[j + pow2[i - 1]][i - 1]) ? rmq[j][i - 1]
						: rmq[j + pow2[i - 1]][i - 1];
			}
		}
	}

	public int Query(int s, int t) {
		int k = 1, d = t - s + 1, cnt = -1;
		while (k <= d) {
			k *= 2;
			cnt++;
		}
		return compare(rmq[s][cnt], rmq[t - pow2[cnt] + 1][cnt]) ? rmq[s][cnt]
				: rmq[t - pow2[cnt] + 1][cnt];
	}

	private boolean compare(int i, int j) {
		return a[i] < a[j];
	}
}
